#include <stdio.h>
#include <stdlib.h>
#include <csp_spu.h>
#include <csp_debug.h>

/*
 * Test must:
 * 	1) Build a stack
 * 	2) Use globale initialized (.data)
 * 	3) Remember changed values after a yield
 */
int global_pid;

#define NUM_ITEMS 50

void merge(int numbers[], int temp[], int left, int mid, int right) {
	int i, left_end, num_elements, tmp_pos;

	left_end = mid - 1;
	tmp_pos = left;
	num_elements = right - left + 1;

	while ((left <= left_end) && (mid <= right)) {
		if (numbers[left] <= numbers[mid]) {
			temp[tmp_pos] = numbers[left];
			tmp_pos = tmp_pos + 1;
			left = left +1;
		} else {
			temp[tmp_pos] = numbers[mid];
			tmp_pos = tmp_pos + 1;
			mid = mid + 1;
		}
	}

	while (left <= left_end) {
		temp[tmp_pos] = numbers[left];
		left = left + 1;
		tmp_pos = tmp_pos + 1;
	}
	while (mid <= right) {
		temp[tmp_pos] = numbers[mid];
		mid = mid + 1;
		tmp_pos = tmp_pos + 1;
	}

	for (i=0; i <= num_elements; i++) {
		numbers[right] = temp[right];
		right = right - 1;
	}
}


void m_sort(int numbers[], int temp[], int left, int right) {
	int mid;

	if (right > left) {
		mid = (right + left) / 2;
		m_sort(numbers, temp, left, mid);
		m_sort(numbers, temp, mid+1, right);

		merge(numbers, temp, left, mid+1, right);
	}
}

void sort(int numbers[], int temp[], int array_size) {
	m_sort(numbers, temp, 0, array_size - 1);
}

int Run(){
	int i, val;
	int pid = csp_pid();
	global_pid = csp_pid();

	int temp[NUM_ITEMS];


	int data[] = 
	   {88403, 87928, 83214, 81314, 78000, 76876, 76402, 74309, 73980, 
		73130, 70814, 70719, 69556, 68849, 67013, 65606, 64972, 64059, 
		61109, 60650, 60244, 57621, 55073, 53343, 52978, 51523, 49822, 
		49381, 48496, 48162, 46655, 45771, 41090, 40390, 37332, 30176, 
		30150, 29408, 29062, 28964, 27730, 19614, 19169, 18825, 15814, 
		8133, 7428, 7194, 6813, 2509};

	PRINTF_FOR_TESTING("mergesort_task starting on spe #%i with pid %i\n", csp_spe_id(), pid);
	val = 100000;
	//PRINTF_FOR_TESTING("Before mergesort: ");
	for(i = 0; i < NUM_ITEMS; i++){
		ASSERT( val > data[i] );
		val = data[i];
		//PRINTF_FOR_TESTING("%i ", data[i]);
	}
	//PRINTF_FOR_TESTING("\n");


	sort(data, temp, NUM_ITEMS);

	val = -1;
	//PRINTF_FOR_TESTING("After mergesort: ");
	for(i = 0; i < NUM_ITEMS; i++){
		ASSERT( val < data[i] );
		val = data[i];
		//PRINTF_FOR_TESTING("%i ", data[i]);
	}
	//PRINTF_FOR_TESTING("\n");

	ASSERT( pid == csp_pid() );
	ASSERT( global_pid == csp_pid() );

	PRINTF_FOR_TESTING("mergesort_task terminating on spe #%i with pid %i\n", csp_spe_id(), pid);
	return 88732;
}

